﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Sokoban.ViewModel.Boxes;

namespace Sokoban.ViewModel
{
    class Node
    {
        public int[] boxRow;
        public int[] boxCol;
        public int boxCount;
        public int playerRow;
        public int playerCol;
        public int depth;
        public bool isThereBox(int row, int col)
        {
            for (int i = 0; i < boxCount; i++)
                if ((boxRow[i] == row) && (boxCol[i] == col))
                    return true;
            return false;
        }
        public int whichBox(int row, int col)
        {            
            for (int i = 0; i < boxCount; i++)
                if ((boxRow[i] == row) && (boxCol[i] == col))
                    return i;
            return -1;
        }
        public bool NodeEquality(Node other)
        {
            if ((this.playerRow != other.playerRow) || (this.playerCol != other.playerCol))
                return false;
            for (int i = 0; i < boxCount; i++)
                if (!isThereBox(other.boxRow[i], other.boxCol[i]))
                    return false;
            return true;
        }
    }
    class Solver
    {
        List<Node> open = new List<Node>();
        List<Node> deeper = new List<Node>();
        List<Node> closed = new List<Node>();        
        public int[] goalRow;
        public int[] goalCol;
        public int goalCount;
        public bool[,] walls; //T:Empty, F:Wall
        public int maxRow;
        public int maxCol;
        public int maxDepth;
        public int depthStep;
        public int finalDepth;
        public bool goalState(Node node)
        {
            for (int i = 0; i < goalCount; i++)
                if (!node.isThereBox(goalRow[i], goalCol[i]))
                    return false;
            return true;
        }
        public Solver(BoxViewModel[,] boxMatrix,int firstDepth, int depthStep, int finalDepth)
        {
            this.maxDepth = firstDepth;
            this.depthStep = depthStep;
            this.finalDepth = finalDepth;
            this.maxRow = boxMatrix.GetLength(0);
            this.maxCol = boxMatrix.GetLength(1);
            this.walls = new bool[maxRow, maxCol];
            List<int> boxesRC = new List<int>();
            List<int> goalsRC = new List<int>();
            this.goalCount = 0;
            Node firstNode = new Node();
            firstNode.boxCount = 0;
            for (int r = 0; r < maxRow; r++)
                for (int c = 0; c < maxCol; c++)
                {
                    if (boxMatrix[r, c].Box is Player)
                    {
                        firstNode.playerRow = r;
                        firstNode.playerCol = c;                        
                    }
                    if (boxMatrix[r, c].Box is Box)
                    {
                        firstNode.boxCount++;
                        boxesRC.Add(r);
                        boxesRC.Add(c);                        
                    }
                    if (boxMatrix[r, c].Box is Goal)
                    {
                        this.goalCount++;
                        goalsRC.Add(r);
                        goalsRC.Add(c);                     
                    }
                    if (boxMatrix[r, c].Box is Wall)                    
                        this.walls[r, c] = false;
                    else                    
                        this.walls[r, c] = true;                        
                }
            firstNode.boxRow = new int[firstNode.boxCount];
            firstNode.boxCol = new int[firstNode.boxCount];
            int li = 0;
            int bi = 0;
            while(li<boxesRC.Count)
            {
                firstNode.boxRow[bi] = boxesRC[li++];
                firstNode.boxCol[bi++] = boxesRC[li++];
            }
            goalRow = new int[goalCount];
            goalCol = new int[goalCount];
            li = 0;
            bi = 0;
            while (li < goalsRC.Count)
            {
                goalRow[bi] = goalsRC[li++];
                goalCol[bi++] = goalsRC[li++];
            }
            open.Add(firstNode);
        }
        public void FreeStep(Node node,int playerR, int playerC)
        {
            if (node.depth + 1 <= finalDepth)
            {
                Node newNode = new Node();
                newNode.playerRow = playerR;
                newNode.playerCol = playerC;
                newNode.depth = node.depth + 1;
                newNode.boxCount = node.boxCount;
                newNode.boxRow = new int[newNode.boxCount];
                newNode.boxCol = new int[newNode.boxCount];
                for (int i = 0; i < node.boxCount; i++)
                {
                    newNode.boxRow[i] = node.boxRow[i];
                    newNode.boxCol[i] = node.boxCol[i];
                }
                if (!IsDuplicatedNode(newNode))
                {
                    if (newNode.depth > maxDepth)
                        deeper.Add(newNode);
                    else
                        open.Add(newNode);
                }
            }
        }
        public void PushBox(Node node, int playerR,int playerC, int boxR, int boxC)
        {
            int boxnum = node.whichBox(playerR,playerC);
            if (node.depth + 1 <= finalDepth)
            {
                Node newNode = new Node();
                newNode.playerRow = playerR;
                newNode.playerCol = playerC;
                newNode.depth = node.depth + 1;
                newNode.boxCount = node.boxCount;
                newNode.boxRow = new int[newNode.boxCount];
                newNode.boxCol = new int[newNode.boxCount];
                for (int i = 0; i < node.boxCount; i++)
                {
                    if (i == boxnum)
                    {
                        newNode.boxRow[i] = boxR;
                        newNode.boxCol[i] = boxC;
                    }
                    else
                    {
                        newNode.boxRow[i] = node.boxRow[i];
                        newNode.boxCol[i] = node.boxCol[i];
                    }
                }
                if (!IsDuplicatedNode(newNode))
                {
                    if (newNode.depth > maxDepth)
                        deeper.Add(newNode);
                    else
                        open.Add(newNode);
                }
            }
        }
        public bool InRange(int row, int col)
        {
            if ((row >= 0) && (row < maxRow) && (col >= 0) && (col < maxCol))
                return true;
            return false;
        }
        public void OpenNode(Node node, int index)
        {
            if (!NodeInDeadlock(node))
            {
                if (InRange(node.playerRow - 1, node.playerCol)) //Up
                {
                    int newRow = node.playerRow - 1;
                    int newCol = node.playerCol;
                    int newBoxR = node.playerRow - 2;
                    int newBoxC = node.playerCol;
                    if (walls[newRow, newCol])
                    {
                        if (node.isThereBox(newRow, newCol))
                        {
                            if ((InRange(newBoxR, newBoxC)) && (walls[newBoxR, newBoxC]) && (!node.isThereBox(newBoxR, newBoxC)))
                            {
                                PushBox(node, newRow, newCol, newBoxR, newBoxC);
                            }
                        }
                        else
                            FreeStep(node, newRow, newCol);
                    }
                }
                if (InRange(node.playerRow + 1, node.playerCol)) //Down
                {
                    int newRow = node.playerRow + 1;
                    int newCol = node.playerCol;
                    int newBoxR = node.playerRow + 2;
                    int newBoxC = node.playerCol;
                    if (walls[newRow, newCol])
                    {
                        if (node.isThereBox(newRow, newCol))
                        {
                            if ((InRange(newBoxR, newBoxC)) && (walls[newBoxR, newBoxC]) && (!node.isThereBox(newBoxR, newBoxC)))
                            {
                                PushBox(node, newRow, newCol, newBoxR, newBoxC);
                            }
                        }
                        else
                            FreeStep(node, newRow, newCol);
                    }
                }
                if (InRange(node.playerRow, node.playerCol - 1)) //Left
                {
                    int newRow = node.playerRow;
                    int newCol = node.playerCol - 1;
                    int newBoxR = node.playerRow;
                    int newBoxC = node.playerCol - 2;
                    if (walls[newRow, newCol])
                    {
                        if (node.isThereBox(newRow, newCol))
                        {
                            if ((InRange(newBoxR, newBoxC)) && (walls[newBoxR, newBoxC]) && (!node.isThereBox(newBoxR, newBoxC)))
                            {
                                PushBox(node, newRow, newCol, newBoxR, newBoxC);
                            }
                        }
                        else
                            FreeStep(node, newRow, newCol);
                    }
                }
                if (InRange(node.playerRow, node.playerCol + 1)) //Right
                {
                    int newRow = node.playerRow;
                    int newCol = node.playerCol + 1;
                    int newBoxR = node.playerRow;
                    int newBoxC = node.playerCol + 2;
                    if (walls[newRow, newCol])
                    {
                        if (node.isThereBox(newRow, newCol))
                        {
                            if ((InRange(newBoxR, newBoxC)) && (walls[newBoxR, newBoxC]) && (!node.isThereBox(newBoxR, newBoxC)))
                            {
                                PushBox(node, newRow, newCol, newBoxR, newBoxC);
                            }
                        }
                        else
                            FreeStep(node, newRow, newCol);
                    }
                }
            }
            closed.Add(node);
            open.RemoveAt(index);
        }
        public bool IsDuplicatedNode(Node node)
        {
            for (int i = 0; i < open.Count; i++)
                if (open[i].NodeEquality(node))
                    return true;
            for (int i = 0; i < deeper.Count; i++)
                if (deeper[i].NodeEquality(node))
                    return true;
            for (int i = 0; i < closed.Count; i++)
                if (closed[i].NodeEquality(node))
                    return true;
            return false;
        }
        public int ChooseNextNode()
        {
            if (open.Count > 0)
                return open.Count - 1;
            else
                return -1;
        }
        public void GoingDeeper()
        {
            maxDepth += depthStep;
            if (finalDepth < maxDepth)
                maxDepth = finalDepth;
        }
        public bool CanBeSolvedThisMap()
        {
            while (open.Count+deeper.Count>0)
            {
                int nodeIndex = ChooseNextNode();
                if (nodeIndex >= 0)
                {
                    Node node = open[nodeIndex];
                    if (goalState(node))
                        return true;
                    OpenNode(node, nodeIndex);
                }
                else
                {
                    GoingDeeper();
                }
            }
            return false;
        }
        public bool isThereGoal(int row, int col)
        {
            for (int i = 0; i < goalCount; i++)
                if ((goalRow[i] == row) && (goalCol[i] == col))
                    return true;
            return false;
        }
        public bool NodeInDeadlock(Node node)
        {
            for (int i = 0; i < node.boxCount; i++)
            {
                int row = node.boxRow[i];
                int col = node.boxCol[i];
                if (!isThereGoal(row,col))
                {
                    if ((!walls[row - 1, col]) && (!walls[row, col + 1]))
                        return true;
                    if ((!walls[row, col + 1]) && (!walls[row + 1, col]))
                        return true;
                    if ((!walls[row + 1, col]) && (!walls[row, col - 1]))
                        return true;
                    if ((!walls[row, col - 1]) && (!walls[row - 1, col]))
                        return true;
                }            
            }
            return false;
        }
    }
} 
